Digital data in electronic devices and systems is often subject to noise and disturbances when transported through various data channels. Such data channels may include a data transmission line, a wireless link (e.g., an RF or optical link), or a storage medium (e.g., a CDROM). Data that is transmitted in telephone lines, for example, may be disturbed by thermal noise or lightning. Data stored on a magnetic medium such as a floppy disk may contain errors caused by defects in the disk. Therefore, data may not be perfectly reproduced by these data channels.
Error-correcting codes have been developed and used in various data communication systems to mitigate this problem. Source information data is encoded to form encoded data ("code words") based on a set of error-correcting codes. The encoded data has additional digits that are used to detect and correct errors. The encoded data is then transmitted through a noisy data channel and is decoded at a receiving end to recover the original source information data.
Design of proper error-correcting codes to achieve certain error-correcting capability is a complex and formidable task. Many classical coding techniques use linear codes. A pack of k-bit data is encoded to form code words of n bits (n&gt;k) in word length. The k-bit data may be represented by a k-dimensional binary vector .upsilon.. A generator matrix G can be formed according to a coding algorithm so that G.upsilon. is the coded data. The columns of G form a basis for the k-dimensional coding subspace of the n-dimensional binary vector space and represent basis code words. The name "linear" is used since a general code word can be an arbitrary linear combination of the basis code words.
Quantum-mechanical systems have been investigated for information processing such as quantum computation and quantum cryptography. A suitable quantum system has an ensemble of subsystems with two quantum states where subsystems are strongly correlated due to non-local quantum coherence. Each two-state subsystem is called a quantum bit ("qubit"). Information can be represented, stored, processed, and transmitted by superposition and correlation of different qubits. Such quantum information processing systems may outperform electronic computers in certain tasks such as prime factorization problems.
Many implementations of qubits have been proposed or demonstrated. For example, the ground and excited states of ions trapped in a linear ion trap can be used to form quantum logic gates. Interaction between trapped ions can be realized by a joint vibrational mode. Cirac and Zoller, "Quantum computations with cold trapped ions," Phys. Rev. Lett. 74, pp. 4091-4094 (1995) and Monroe et al. "Demonstration of a fundamental quantum logic gate," Phys. Rev. Lett., 75, pp. 4714-4717 (1995). Quantum logic gates can also be formed by polarization of photons in cavity quantum electrodynamics systems. Turchette et al., "Measurement of conditional phase shifts for quantum logic," Phys. Rev. Lett., 75, pp. 4710-4713 (1995). Furthermore, nuclear-spin states in polymers are used to form quantum logic gates in which the interactions are provided by nuclear magnetic resonance. Gershenfeld and Chuang, "Bulk spin resonance quantum computation," Science 275, pp. 350(1995).
These and other quantum systems are susceptible to perturbation caused by environment, measurement and other factors. Entangled states are in general delicate and may be easily corrupted by any external perturbation to become less entangled states. Hence, perturbation causes errors since data are represented by the entangled states. One solution uses quantum error-correcting codes similar to the error-correcting codes in the classical computers or electronic data processors.
However, many classical error-correcting coding techniques cannot be directly applied to quantum systems. Classical coding techniques assume all of the data bits can be precisely measured. Such measurement cannot be performed in quantum systems since any entanglement between qubits would be destroyed. Further, classical computers only need to preserve the bit values of 0 and 1 but quantum systems need to keep both relative amplitude and phase of entangled states due to the quantum coherence. Therefore, quantum error-correcting codes require different design approaches from their classical counterparts.
Shor disclosed a quantum error-correcting code to represent data in 9 qubits for correcting a single bit error in "Scheme for reducing decoherence in quantum memory," Phys. Rev. A52, pp. R2493-R2496(1995). Steane discovered another quantum error-correcting code based on qubits in two mutually rotated bases. See, Steane, "Error correcting codes in quantum theory," Phys. Rev. Lett. 77, pp. 793-797(1996).